
#define divnorm(num, den, sign) 		\
{						\
  if (num < 0) 					\
    {						\
      num = -num;				\
      sign = 1;					\
    }						\
  else 						\
    {						\
      sign = 0;					\
    }						\
						\
  if (den < 0) 					\
    {						\
      den = - den;				\
      sign = 1 - sign;				\
    } 						\
}





static unsigned long divmodsi4(int modwanted, unsigned long num, unsigned long den)	
{						
  long int bit = 1;				
  long int res = 0;				
  long prevden;
  while (den < num && bit && !(den & (1L<<31)))			       
    {
      den <<=1;					
      bit <<=1;					
    }						
  while (bit)
    {					
      if (num >= den)
	{				
	  num -= den;				
	  res |= bit;				
	}						
      bit >>=1;					
      den >>=1;					
    }						
  if (modwanted) return num;
  return res;
}


#define exitdiv(sign, res) if (sign) { res = - res;} return res;

long __modsi3 (long numerator, long denominator)
{
  int sign = 0;
  long dividend;
  long modul;


  if (numerator < 0) 
    {
      numerator = -numerator;
      sign = 1;
    }
  if (denominator < 0)
    {
      denominator = -denominator;
    }  
  
  modul =  divmodsi4 (1, numerator, denominator);
  if (sign)
    return - modul;
  return modul;
}


long __divsi3 (long numerator, long denominator)
{
  int sign;
  long dividend;
  long modul;
  divnorm (numerator, denominator, sign);

  dividend = divmodsi4 (0,  numerator, denominator);
  exitdiv (sign, dividend);
}

long __umodsi3 (unsigned long numerator, unsigned long denominator)
{
  long dividend;
  long modul;

modul= divmodsi4 (1,  numerator, denominator);
  return modul;
}

long __udivsi3 (unsigned long numerator, unsigned long denominator)
{
  int sign;
  long dividend;
  long modul;
  dividend =   divmodsi4 (0, numerator, denominator);
  return dividend;
}




unsigned long long __umoddi3(unsigned long long a, unsigned long long b){
    unsigned long long tempah = 0;
    unsigned long long tempal = a;

    unsigned long long tempbh = b;
    unsigned long long tempbl = 0;

    unsigned long long q = 0;
    int i;
    for (i = 0; i <= 64; i++)
    {
        q <<= 1;
        if ((tempah > tempbh) || (tempah == tempbh && tempal >= tempbl))
        {
            //tempa -= tempb;
            if (tempal < tempbl)
            {
                tempah--;
            }
            tempal -= tempbl;
            tempah -= tempbh;
            q++;
        }
        //tempb >>= 1;
        tempbl >>= 1;
        if ((tempbh & 1) == 1) {
            tempbl |= 0x8000000000000000LL;
        }
        tempbh >>= 1;
    }
    unsigned long long rem = tempal;
    return rem;
}

unsigned long long __udivdi3(unsigned long long a, unsigned long long b){
    unsigned long long tempah = 0;
    unsigned long long tempal = a;

    unsigned long long tempbh = b;
    unsigned long long tempbl = 0;

    unsigned long long q = 0;
    int i;
    for (i = 0; i <= 64; i++)
    {
        q <<= 1;
        if ((tempah > tempbh) || (tempah == tempbh && tempal >= tempbl))
        {
            //tempa -= tempb;
            if (tempal < tempbl)
            {
                tempah--;
            }
            tempal -= tempbl;
            tempah -= tempbh;
            q++;
        }
        //tempb >>= 1;
        tempbl >>= 1;
        if ((tempbh & 1) == 1) {
            tempbl |= 0x8000000000000000LL;
        }
        tempbh >>= 1;
    }
    return q;
}



long long __moddi3(long long a, long long b){
    int sa;
    int sb;
    unsigned long long tempah = 0;
    unsigned long long tempal;
    if(a>=0){
      sa = 0;
      tempal = a;
    }else{
      sa = 1;
      tempal = -a;
    }
    
    unsigned long long tempbh = b;
    unsigned long long tempbl = 0;
    if(b>=0){
      sb = 0;
      tempbh = b;
    }else{
      sb = 1;
      tempbh = -b;
    }
    
    unsigned long long q = 0;
    int i;
    for (i = 0; i <= 64; i++)
    {
        q <<= 1;
        if ((tempah > tempbh) || (tempah == tempbh && tempal >= tempbl))
        {
            //tempa -= tempb;
            if (tempal < tempbl)
            {
                tempah--;
            }
            tempal -= tempbl;
            tempah -= tempbh;
            q++;
        }
        //tempb >>= 1;
        tempbl >>= 1;
        if ((tempbh & 1) == 1) {
            tempbl |= 0x8000000000000000LL;
        }
        tempbh >>= 1;
    }
    long long ret;
    if((sa ^ sb)==0){
      ret = tempal;
    }else{
      ret = -tempal;
    }
    return ret;
}


long long __divdi3(long long a, long long b){
    int sa;
    int sb;
    unsigned long long tempah = 0;
    unsigned long long tempal;
    if(a>=0){
      sa = 0;
      tempal = a;
    }else{
      sa = 1;
      tempal = -a;
    }
    
    unsigned long long tempbh = b;
    unsigned long long tempbl = 0;
    if(b>=0){
      sb = 0;
      tempbh = b;
    }else{
      sb = 1;
      tempbh = -b;
    }
    
    unsigned long long q = 0;
    int i;
    for (i = 0; i <= 64; i++)
    {
        q <<= 1;
        if ((tempah > tempbh) || (tempah == tempbh && tempal >= tempbl))
        {
            //tempa -= tempb;
            if (tempal < tempbl)
            {
                tempah--;
            }
            tempal -= tempbl;
            tempah -= tempbh;
            q++;
        }
        //tempb >>= 1;
        tempbl >>= 1;
        if ((tempbh & 1) == 1) {
            tempbl |= 0x8000000000000000LL;
        }
        tempbh >>= 1;
    }
    long long ret;
    if((sa ^ sb)==0){
      ret = q;
    }else{
      ret = -q;
    }
    return ret;
}

typedef union{
	long long all;
	struct{
		unsigned int low;
		int high;
	}s;
} dwords;
 
long long __muldsi3(unsigned int a, unsigned int b){
	dwords r;
 
	const int bits_in_word_2 = (int)(sizeof(int) * 8) / 2;
	const unsigned int lower_mask = (unsigned int)~0 >> bits_in_word_2;
	r.s.low = (a & lower_mask) * (b & lower_mask);
	unsigned int t = r.s.low >> bits_in_word_2;
	r.s.low &= lower_mask;
	t += (a >> bits_in_word_2) * (b & lower_mask);
	r.s.low += (t & lower_mask) << bits_in_word_2;
	r.s.high = t >> bits_in_word_2;
	t = r.s.low >> bits_in_word_2;
	r.s.low &= lower_mask;
	t += (b >> bits_in_word_2) * (a & lower_mask);
	r.s.low += (t & lower_mask) << bits_in_word_2;
	r.s.high += t >> bits_in_word_2;
	r.s.high += (a >> bits_in_word_2) * (b >> bits_in_word_2);
 
	return r.all;
}
 
long long __muldi3(long long a, long long b){
	dwords x;
	x.all = a;
	dwords y;
	y.all = b;
	dwords r;
	r.all = __muldsi3(x.s.low, y.s.low);
	/*  r.s.high += x.s.high * y.s.low + x.s.low * y.s.high; */
	r.s.high += x.s.high * y.s.low + x.s.low * y.s.high;
 
	return r.all;
}


unsigned int __clzdi2(unsigned long long v)
{
	int p = 63;

	if (v & 0xffffffff00000000ULL) {
		p -= 32;
		v >>= 32;
	}
	if (v & 0xffff0000UL) {
		p -= 16;
		v >>= 16;
	}
	if (v & 0xff00) {
		p -= 8;
		v >>= 8;
	}
	if (v & 0xf0) {
		p -= 4;
		v >>= 4;
	}
	if (v & 0xc) {
		p -= 2;
		v >>= 2;
	}
	if (v & 0x2) {
		p -= 1;
		v >>= 1;
	}

	return p;
}


int __ctzsi2(int a)
{
    unsigned int x = (unsigned int)a;
    int t = ((x & 0x0000FFFF) == 0) << 4;  /* if (x has no small bits) t = 16 else 0 */
    x >>= t;           /* x = [0 - 0xFFFF] + higher garbage bits */
    unsigned int r = t;       /* r = [0, 16]  */
    /* return r + ctz(x) */
    t = ((x & 0x00FF) == 0) << 3;
    x >>= t;           /* x = [0 - 0xFF] + higher garbage bits */
    r += t;            /* r = [0, 8, 16, 24] */
    /* return r + ctz(x) */
    t = ((x & 0x0F) == 0) << 2;
    x >>= t;           /* x = [0 - 0xF] + higher garbage bits */
    r += t;            /* r = [0, 4, 8, 12, 16, 20, 24, 28] */
    /* return r + ctz(x) */
    t = ((x & 0x3) == 0) << 1;
    x >>= t;
    x &= 3;            /* x = [0 - 3] */
    r += t;            /* r = [0 - 30] and is even */
    /* return r + ctz(x) */

/*  The branch-less return statement below is equivalent
 *  to the following switch statement:
 *     switch (x)
 *    {
 *     case 0:
 *         return r + 2;
 *     case 2:
 *         return r + 1;
 *     case 1:
 *     case 3:
 *         return r;
 *     }
 */
    return r + ((2 - (x >> 1)) & -((x & 1) == 0));
}